/*
 * Given a circular linked list, implement an algorithm which returns node at the beginning of the loop.
 * DEFINITION
 * Circular linked list: A (corrupt) linked list in which a node's next pointer points to an earlier node, 
 * so as to make a loop in the linked list
 * EXAMPLE
 * input: A->B->C->D->E->C [the same C as earlier]
 * output: C
 */
package Chapter2;

public class Chapter2_5 {

	public MyLinkedListNode findLoopStart(MyLinkedListNode head)
	{
		if(head == null) return null;
		MyLinkedListNode slow = head;
		MyLinkedListNode fast = head;
		slow = slow.Next;
		if(slow == null) return null; //only one node in list and no loop
		fast = fast.Next.Next;
		if(fast == null) return null; 
		while(fast.Next != null)
		{
			slow = slow.Next;
			
			fast = fast.Next.Next;
			if(slow == fast)
				break;
		}
		if(fast.Next == null) return null;
		MyLinkedListNode meet = slow;
		
		slow = head;
		while(slow != meet)
		{
			slow = slow.Next;
			meet = meet.Next;
		}
		
		return slow;
	}
	
	public static void main(String args[])
	{
		MyLinkedListNode node1 = new MyLinkedListNode(1);
		MyLinkedListNode node2 = new MyLinkedListNode(2);
		MyLinkedListNode node3 = new MyLinkedListNode(3);
		MyLinkedListNode node4 = new MyLinkedListNode(4);
		MyLinkedListNode node5 = new MyLinkedListNode(5);
		MyLinkedListNode node6 = new MyLinkedListNode(6);
		MyLinkedListNode node7 = new MyLinkedListNode(7);
		
		node1.Next = node2;
		node2.Next = node3;
		node3.Next = node4;
		node4.Next = node5;
		node5.Next = node6;
		node6.Next = node7;
		node7.Next = node7;
		
		Chapter2_5 test = new Chapter2_5();
		MyLinkedListNode result = test.findLoopStart(node1);
		if(result != null)
			System.out.println("2_5:" + result.value);
		else
			System.out.println("2_5: no loop");
		
	}
}
